---
title: "填涂颜色"
created: 2025-11-28
tags:
  - 算法
---

# 填涂颜色

## 题目 [填涂颜色](https://www.luogu.com.cn/problem/P1162)

![[image-0f5655e5.png]]

## 思路分析

![[image-f443ec2c.png]]

![[image-6b171ee2.png]]

即使圈长这样 也只需要一桶油漆就可以标记出来

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=35;

int g[N][N];

bool st[N][N];

int n;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=n-1 && !st[x][y];

}

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==0){

				q.push({nx,ny});

				st[nx][ny]=true;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=0;i<n;i++){

		for(int j=0;j<n;j++){

			cin>>g[i][j];

		}

	}

	bfs(0,0);

	for(int i=0;i<n;i++){

		for(int j=0;j<n;j++){

			if(g[i][j]==0 && !st[i][j]){

				g[i][j]=2;

			}

			cout<<g[i][j]<<" ";

		}

		cout<<endl;

	}

	return 0;

}
```

![[image-835939fc.png]]

发现出问题了

其实不能简单从0,0开始倒油漆

若00处是1的话 显然就有问题了

那在边框搜一圈 在边框发现0就倒颜料呢？

好像也不行 若最外圈都是1（即所有的0都在1里面） 就又不行了

那怎么办

没有办法就创作办法 没有0 我就自己在外面加一圈0呗

反正最后被1包住的0又不会受影响

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=35;

int g[N][N];

bool st[N][N];

int n;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){//整个加一圈 数据在1~n 加上一圈0~n+1

	return x>=0 && x<=n+1 && y>=0 && y<=n+1 && !st[x][y];

}

void bfs(int x,int y){

	queue<PII> q;

	q.push({x,y});

	st[x][y]=true;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<4;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny) && g[nx][ny]==0){

				q.push({nx,ny});

				st[nx][ny]=true;

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			cin>>g[i][j];

		}

	}

	bfs(0,0);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			if(g[i][j]==0 && !st[i][j]){

				g[i][j]=2;

			}

		}

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			cout<<g[i][j]<<" ";

		}

		cout<<endl;

	}

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[forgery|forgery]] 🏠 [[00-刷题理模型]] ➡️ [[拯救oibh总部|拯救oibh总部]]